// 提交链接 https://leetcode.cn/problems/time-taken-to-mark-all-nodes/submissions/552539770/
// 3241 标记所有节点需要的时间
// 完成日期： 2024.10.7
// 换根dp
class Solution {
public:
    vector<int> ma[100005];
    int first[100005], second[100005], _max[100005];
    vector<int> timeTaken(vector<vector<int>>& edges) {
        vector<int> ans(edges.size() + 1, 0);
        for (auto& x : edges)
        {
            ma[x[0]].push_back(x[1]);
            ma[x[1]].push_back(x[0]);
        }
        dfs(0, -1);
        ans[0] = first[0];
        for (auto& x : ma[0]) solve(x, 0, ans);
        return ans;
    }
    void solve(int i, int pre, vector<int>& ans)
    {
        int temp;
        if (_max[pre] == i) temp = second[pre];
        else temp = first[pre];
        if (pre % 2) temp += 1;
        else temp += 2;
        if (temp > first[i])
        {
            second[i] = first[i];
            first[i] = temp;
            _max[i] = pre;
        }
        else if (temp > second[i])
        {
            second[i] = temp; 
        }
        ans[i] = first[i];
        for (auto& x : ma[i])
        { 
            if (x == pre) continue;
            solve(x, i, ans);
        }
    }

    int dfs(int i, int pre)
    {
        for (auto& x : ma[i])
        {
            if (x == pre) continue;
            int temp = dfs(x, i);
            if (x % 2) temp += 1;
            else temp += 2;
            if (temp > first[i])
            {
                second[i] = first[i];
                first[i] = temp;
                _max[i] = x;
            }
            else if (temp > second[i])
            {
                second[i] = temp; 
            }
        }
        return first[i];
    }
};